package com.salim.leetcode.$23;


import java.util.PriorityQueue;

/**
 * Compare one by one 很慢
 */
public class MergekSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head;
        Integer min = null;
        int index = 0;
        for (int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                if(min == null || lists[i].val<min){
                    min = lists[i].val;
                    index = i;
                }
            }
        }
        if(min!=null){
            head = new ListNode(lists[index].val);
            if(lists[index].next!=null){
                lists[index] = lists[index].next;
            }else{
                lists[index] = null;
            }
            findMinListNodeAndForward(head,lists);
            return head;
        }else{
            return null;
        }
    }

    public void findMinListNodeAndForward(ListNode head,ListNode[] lists){
        Integer min = null;
        int index = 0;
        for (int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                if(min == null || lists[i].val<min){
                    min = lists[i].val;
                    index = i;
                }
            }
        }
        if(min!=null){
            head.next = lists[index];
            if(lists[index].next!=null){
                lists[index] = lists[index].next;
            }else{
                lists[index] = null;
            }
            findMinListNodeAndForward(head.next,lists);
        }
    }

    public static void main(String[] args) {
        MergekSortedLists mergekSortedLists = new MergekSortedLists();
        ListNode line11 = new ListNode(1);
        ListNode line14 = new ListNode(4);
        ListNode line15 = new ListNode(5);
        ListNode line21 = new ListNode(1);
        ListNode line23 = new ListNode(3);
        ListNode line24 = new ListNode(4);
        ListNode line32 = new ListNode(2);
        ListNode line36 = new ListNode(6);
        line11.next = line14;
        line14.next = line15;
        line21.next = line23;
        line23.next = line24;
        line32.next = line36;
        ListNode[] arrays = {line11,line21,line32};
        ListNode head = mergekSortedLists.mergeKLists(arrays);
        System.out.println(head.toString());
    }
}



class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    @Override
    public String toString() {
        String str =  " ["+this.val+"]";
        if(this.next!=null){
            str += this.next.toString();
        }
        return str;
    }
}

/**
 * 分治法 两两list调用merge two list
 */
class MergewithDivideAndConquer {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0 ) return null;
        int j=1;
        while (j<lists.length){
            for (int i=0; i+j<lists.length;i+=j*2) {
                lists[i] = merge(lists, i, i+j);
            }
            j*=2;
        }
        return lists[0];
    }

    ListNode merge(ListNode[] l, int i, int j) {
        if (j >= l.length) return l[i];
        ListNode dummy = new ListNode();
        ListNode curr = dummy, a = l[i], b = l[j];
        while (a != null && b != null) {
            if (a.val < b.val) {
                curr.next = a;
                curr = curr.next;
                a = a.next;
            } else {
                curr.next = b;
                curr = curr.next;
                b=b.next;
            }
        }
        if (a != null) curr.next =a;
        if (b!=null) curr.next=b;
        return dummy.next;
    }
}

/**
 * 优先队列
 */
class PriorityQueueSolution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> {
            return a.val - b.val;
        });

        for (ListNode list : lists) {
            if (list != null) {
                minHeap.add(list);
            }
        }

        ListNode sentinel = new ListNode(0);
        ListNode node = sentinel;
        while (!minHeap.isEmpty()) {
            ListNode n = minHeap.remove();
            node.next = n;
            node = node.next;
            if (n.next != null) minHeap.add(n.next);
        }

        return sentinel.next;
    }
}
